package com.blue.basic.data.blf_test;

/**
 * 最大堆：只保证父节点比字节点大
 *
 * @author liulei, lei.liu@htouhui.com
 * @version 1.0
 */
public class Heap<E extends Comparable> {

    Array<E> data;

    public Heap() {
        data = new Array<>(10);
    }

    public int getSize() {
        return this.data.getSize();
    }

    public void add(E e) {
        this.data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    private E extractMax() {
        //1.0和size-1交换数据位置，删除掉最后一个节点，再从0siftDown
        E max = data.get(0);
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return max;
    }

    public void siftUp(int index) {
        while (parent(index) >= 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) {
            data.swap(parent(index), index);
            index = parent(index);
        }
    }

    private void siftDown(int index) {
        while (leftChild(index) < data.size) {
            int leftIndex = leftChild(index);
            if (rightChild(index) < data.size && data.get(leftIndex).compareTo(data.get(leftIndex + 1)) < 0) {
                leftIndex += 1;
            }
            if (data.get(index).compareTo(data.get(leftIndex)) > 0) {
                break;
            }
            data.swap(index, leftIndex);
            index = leftIndex;
        }
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

    public void printData() {
        System.out.println(this.data.toString());
    }

    public static void main(String[] args) {
        Heap<Integer> heap = new Heap<>();
        heap.add(0);
        heap.add(1);
        heap.add(3);
        heap.add(2);
        heap.add(5);
        heap.printData();
        System.out.println(heap.extractMax());
        heap.printData();
        System.out.println(heap.extractMax());
        heap.printData();
        System.out.println(heap.extractMax());
        heap.printData();
    }
}
